/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月05日
*   描    述：
*
================================================================*/

/*
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti,
 * endi] 。请你合并所有重叠的区间，并返回
 * 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 * 示例 1：
 *   输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 *   输出：[[1,6],[8,10],[15,18]]
 *   解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 示例 2：
 *   输入：intervals = [[1,4],[4,5]]
 *   输出：[[1,5]]
 *   解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 提示：
 *   1 <= intervals.length <= 104
 *   intervals[i].length == 2
 *   0 <= starti <= endi <= 104
 */

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume
 * caller calls free().
 */

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Pair {
  int start;
  int end;
} Pair;

int compare(const void* a, const void* b) {
  return (*(int**)a)[0] - (*(int**)b)[0];
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize,
            int* returnSize, int** returnColumnSizes) {
  // 创建intervalsSize长度的二元组数组ret
  int** ret = (int**)malloc(sizeof(int*) * intervalsSize);
  int retSize = 0;
  *returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize);

  // 将二元组按照首元素的大小进行排序，然后再进行合并操作，合并逻辑是当前二元组的end大于等于下一个二元组的start即可合并。
  qsort(intervals, intervalsSize, sizeof(int*), compare);

  Pair* _srcPair = (Pair*)intervals[0];
  Pair* _beforePair = NULL;

  ret[0] = (int*)malloc(sizeof(Pair));
  ((Pair*)(ret[0]))->start = _srcPair[0].start;
  ((Pair*)(ret[0]))->end = _srcPair[0].end;
  (*returnColumnSizes)[retSize] = 2;
  retSize++;
  for (int i = 1; i < intervalsSize; i++) {
    _beforePair = (Pair*)(ret[retSize - 1]);
    // 合并
    _srcPair = (Pair*)intervals[i];
    if (_srcPair->start <= _beforePair->end) {
      _beforePair->start = _beforePair->start > _srcPair->start
                               ? _srcPair->start
                               : _beforePair->start;
      _beforePair->end =
          _beforePair->end > _srcPair->end ? _beforePair->end : _srcPair->end;
    } else {  // 无交集，不合并
      ret[retSize] = (int*)malloc(sizeof(Pair));
      ((Pair*)(ret[retSize]))->start = _srcPair->start;
      ((Pair*)(ret[retSize]))->end = _srcPair->end;
      (*returnColumnSizes)[retSize] = 2;
      retSize++;
    }
  }
  *returnSize = retSize;
  return ret;
}

int main() {
  // 定义输入区间
  // int intervals[][2] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
  int intervals[][2] = {{1, 4}, {0, 0}};
  int intervalsSize = sizeof(intervals) / sizeof(intervals[0]);

  // 转换为int**格式，因为merge函数需要这种格式
  int** intervalsPtr = (int**)malloc(intervalsSize * sizeof(int*));
  for (int i = 0; i < intervalsSize; i++) {
    intervalsPtr[i] = (int*)malloc(2 * sizeof(int));
    intervalsPtr[i][0] = intervals[i][0];
    intervalsPtr[i][1] = intervals[i][1];
  }

  // 准备传递给merge函数的参数
  int* intervalsColSize = (int*)malloc(intervalsSize * sizeof(int));
  for (int i = 0; i < intervalsSize; i++) {
    intervalsColSize[i] = 2;  // 每个区间都有两个元素
  }
  int returnSize;
  int* returnColumnSizes;

  // 调用merge函数
  int** result = merge(intervalsPtr, intervalsSize, intervalsColSize,
                       &returnSize, &returnColumnSizes);

  // 打印合并后的区间
  for (int i = 0; i < returnSize; i++) {
    printf("[%d, %d]\n", result[i][0], result[i][1]);
  }

  // 释放所有动态分配的内存
  for (int i = 0; i < intervalsSize; i++) {
    free(intervalsPtr[i]);
  }
  free(intervalsPtr);
  free(intervalsColSize);
  for (int i = 0; i < returnSize; i++) {
    free(result[i]);
  }
  free(result);
  free(returnColumnSizes);

  return 0;
}